import java.util.ArrayList;
import java.util.List;

/**
 * 763. 划分字母区间
 * https://leetcode-cn.com/problems/partition-labels/
 */
public class Solutions_763 {
    public static void main(String[] args) {
//        String S = "ababcbacadefegdehijhklij";  // output: {9, 7, 8}
        String S = "ababcbaca";  // output: {9}
        List<Integer> result = partitionLabels(S);
        System.out.println(result);
    }

    public static List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        // map[0] = 10，表示字符 'a' 最后一次出现的索引为 10
        int[] map = new int[26];
        // 字符串，转化成字符数组进行操作
        char[] arr = S.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            map[arr[i] - 'a'] = i;
        }
        int i = 0;
        while (i < arr.length) {
            char c = arr[i];
            // 字符 c 最后一次出现的索引，故最小区间为：[i, lastIndex]
            int lastIndex = map[c - 'a'];
            if (lastIndex == arr.length - 1) {
                // 提前结束循环：若 [i, arr.length - 1] 是一个片段，就不用比较了，区间无法再扩展
                res.add(arr.length - i);
                break;
            }
            // 循环判断 [i, lastIndex] 区间中的字符元素，其最后一次出现位置
            // 是否也在区间内。否则，闭区间向后扩展
            for (int j = i + 1; j < lastIndex; j++) {
                // 判断字符 k 的最后一次出现索引，是否在区间内
                char k = arr[j];
                if (map[k - 'a'] > lastIndex) {
                    // 区间范围扩大
                    lastIndex = map[k - 'a'];
                }
            }
            // 记录下 [i, lastIndex] 区间内元素的个数，该区间即是一个划分正确的片段
            res.add(lastIndex - i + 1);
            // 划分下一个片段
            i = lastIndex + 1;
        }
        return res;
    }
}
